{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #One Away LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: oneEditAway"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #一次编辑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> \n",
    "first = \"pale\"\n",
    "second = \"ple\"\n",
    "<strong>输出:</strong> True</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> \n",
    "first = \"pales\"\n",
    "second = \"pal\"\n",
    "<strong>输出:</strong> False\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [one-away-lcci](https://leetcode.cn/problems/one-away-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [one-away-lcci](https://leetcode.cn/problems/one-away-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first)-len(second)) >1:\n",
    "            return False\n",
    "        l = max(first,second,key=len)\n",
    "        s = min(second,first,key=len)\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==l[i]:\n",
    "                pass\n",
    "            else:\n",
    "                return s[i+1:]==l[i+1:] or s[i:]==l[i+1:] \n",
    "        return True\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m=len(first)\n",
    "        n=len(second)\n",
    "        if abs(m-n)>1:\n",
    "            return False\n",
    "        edited=False\n",
    "        i,j=0,0\n",
    "        while i<m and j<n:\n",
    "            if first[i]==second[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "            elif edited:\n",
    "                return False\n",
    "            else:\n",
    "                if m>n:\n",
    "                    i+=1\n",
    "                elif m<n:\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                edited=True\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        if m < n:\n",
    "            return self.oneEditAway(second, first)\n",
    "        if m - n > 1:\n",
    "            return False\n",
    "        for i, (x, y) in enumerate(zip(first, second)):\n",
    "            if x != y:\n",
    "                return first[i + 1:] == second[i + 1:] if m == n else first[i + 1:] == second[i:]  # 注：改用下标枚举可达到 O(1) 空间复杂度\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        len1, len2 = len(first), len(second)\n",
    "        if abs(len1 - len2) > 1:\n",
    "            return False\n",
    "        if len1 > len2:\n",
    "            first, second = second, first\n",
    "\n",
    "        i, j = 0, 0\n",
    "        edit_count = 0\n",
    "\n",
    "        while i < len(first) and j < len(second):\n",
    "            if first[i] != second[j]:\n",
    "                edit_count += 1\n",
    "                \n",
    "                if len1 == len2:\n",
    "                    i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "            j += 1\n",
    "        return edit_count <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first==second:\n",
    "            return True\n",
    "        m,n=len(first),len(second)\n",
    "        if abs(m-n)>1:\n",
    "            return False\n",
    "        if m==n:\n",
    "            ans=0\n",
    "            for i in range(m):\n",
    "                if first[i]!=second[i]:\n",
    "                    ans+=1\n",
    "                if ans>1:\n",
    "                    break\n",
    "            if ans>1:\n",
    "                return False\n",
    "            return True\n",
    "        if m>n:\n",
    "            first,second=second,first\n",
    "            m,n=n,m\n",
    "        i,j=0,0\n",
    "        while i<m and j<n:\n",
    "            if first[i]==second[j]:\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return i==m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if len(first) < len(second):\n",
    "            first, second = second, first\n",
    "        l1, l2 = len(first), len(second)\n",
    "\n",
    "        # 特判长度\n",
    "        if l1 - l2 > 1:\n",
    "            return False\n",
    "\n",
    "        ptr1, ptr2 = 0, 0\n",
    "        first, second = list(first), list(second)\n",
    "        modified = False\n",
    "        if l1 == l2:  # substitute\n",
    "            while ptr1 < len(first) and ptr2 < len(second):\n",
    "                if first[ptr1] != second[ptr2]:\n",
    "                    if not modified:\n",
    "                        modified = True\n",
    "                    else:\n",
    "                        return False\n",
    "                ptr1 += 1\n",
    "                ptr2 += 1\n",
    "        else:  # add or delete\n",
    "            while ptr1 < len(first) and ptr2 < len(second):\n",
    "                if first[ptr1] == second[ptr2]:\n",
    "                    ptr1 += 1\n",
    "                    ptr2 += 1\n",
    "                else:\n",
    "                    if not modified:\n",
    "                        ptr1 += 1\n",
    "                        modified = True\n",
    "                    else:\n",
    "                        return False\n",
    "        return True\n",
    "# leetcode submit region end(Prohibit modification and deletion)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first == second: return True\n",
    "        for i in range(min(len(first), len(second))):\n",
    "            if first[i] != second[i]:\n",
    "                if len(first) > len(second):\n",
    "                    return first[i+1:] == second[i:]\n",
    "                elif len(first) < len(second):\n",
    "                    return first[i:] == second[i+1:]\n",
    "                else:\n",
    "                    return first[i+1:] == second[i+1:]\n",
    "        return abs(len(first) - len(second)) == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first == second:\n",
    "            return True\n",
    "        elif abs(len(first) - len(second)) > 1:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        # if len(first) == len(second):\n",
    "        #     count = 0\n",
    "        #     for i in range(len(first)):\n",
    "        #         if first[i] != second[i]:\n",
    "        #             count += 1\n",
    "        \n",
    "        else:\n",
    "            i = j = 0\n",
    "            count = 0\n",
    "            while i < len(first) and j < len(second):\n",
    "                if first[i] != second[j]:\n",
    "                    if len(first) > len(second):\n",
    "                        i += 1\n",
    "                    elif len(first) < len(second):\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    count += 1\n",
    "                    continue\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        if count > 1:\n",
    "                return False\n",
    "        else:\n",
    "            return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first == second:\n",
    "            return True\n",
    "        elif abs(len(first) - len(second)) > 1:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        if len(first) == len(second):\n",
    "            count = 0\n",
    "            for i in range(len(first)):\n",
    "                if first[i] != second[i]:\n",
    "                    count += 1\n",
    "        \n",
    "        else:\n",
    "            i = j = 0\n",
    "            count = 0\n",
    "            while i < len(first) and j < len(second):\n",
    "                if first[i] != second[j]:\n",
    "                    if len(first) > len(second):\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        j += 1\n",
    "                    count += 1\n",
    "                    continue\n",
    "                i += 1\n",
    "                j += 1\n",
    "        if count > 1:\n",
    "                return False\n",
    "        else:\n",
    "            return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        if m < n:\n",
    "            return self.oneEditAway(second, first)\n",
    "        if m - n > 1:\n",
    "            return False\n",
    "        for i, (x, y) in enumerate(zip(first, second)):\n",
    "            if x != y:\n",
    "                return first[i+1:] == second[i+1:] if m == n else first[i+1:] == second[i:]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        L1 = len(first)\n",
    "        L2 = len(second)\n",
    "        if first == second:\n",
    "            return True\n",
    "        elif abs(len(first) - len(second)) > 1:\n",
    "            return False\n",
    "        \n",
    "        else:\n",
    "            i = j = 0\n",
    "            count = 0\n",
    "            while i < L1 and j < L2:\n",
    "                if first[i] != second[j]:\n",
    "                    if L1 > L2:\n",
    "                        i += 1\n",
    "                    elif L1 < L2:\n",
    "                        j += 1\n",
    "                    else:\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    count += 1\n",
    "                    continue\n",
    "                i += 1\n",
    "                j += 1\n",
    "        \n",
    "        if count > 1:\n",
    "                return False\n",
    "        else:\n",
    "            return True    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cb(self, longer, shorter):\n",
    "        if shorter == \"\":\n",
    "            return True\n",
    "        for i, (x, y) in enumerate(zip(longer, shorter)):\n",
    "            if x != y:\n",
    "                return longer[i+1:] == shorter[i:]\n",
    "        return True\n",
    "            \n",
    "\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n, m = len(first), len(second)\n",
    "        if abs(n-m) == 1:\n",
    "           if n < m:\n",
    "               return self.cb(second, first)\n",
    "           else:\n",
    "               return self.cb(first, second)\n",
    "\n",
    "        elif abs(n-m) == 0:\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if first[i] != second[i]:\n",
    "                    cnt += 1\n",
    "            if cnt > 1:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first == second:\n",
    "            return True\n",
    "        \n",
    "\n",
    "        def check(first, second, diff):\n",
    "            if not first and not second:\n",
    "                return True\n",
    "            m, n = len(first), len(second)\n",
    "            if m > n:\n",
    "                return check(second, first, diff)\n",
    "            i, j = 0, 0\n",
    "            while i < m:\n",
    "                if first[i] != second[j]:\n",
    "                    if diff:\n",
    "                        return False\n",
    "                    return check(first[i:], second[j+1:], True) or check(first[i+1:], second[j:], True) or check(first[i+1:], second[j+1:], True)\n",
    "                i += 1\n",
    "                j += 1\n",
    "            if n-j == 0:\n",
    "                return True\n",
    "            if n-j == 1 and not diff:\n",
    "                return True\n",
    "            return False\n",
    "        return check(first, second, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "\"\"\"思路一\"\"\"\r\n",
    "class Solution:\r\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\r\n",
    "        len1, len2 = len(first), len(second)\r\n",
    "        if abs(len1 - len2) > 1:   # 两字符串长度之差小于等于1, 才可能一次编辑而相同\r\n",
    "            return False\r\n",
    "        # 始终保证调用参数 len1 <= len2, 便于简化代码\r\n",
    "        if len2 < len1:\r\n",
    "            return self.oneEditAway(second, first)\r\n",
    "\r\n",
    "        p1, p2 = 0, 0\r\n",
    "        diff = 0\r\n",
    "        while p1 < len1 and p2 < len2:\r\n",
    "            if first[p1] != second[p2]:\r\n",
    "                diff += 1\r\n",
    "                if len1 == len2:   # 二者等长\r\n",
    "                    p1 += 1\r\n",
    "                    p2 += 1\r\n",
    "                else:\r\n",
    "                    p2 += 1        # len1更短, 则跳过second[p2], p2后移一位. \r\n",
    "            else:\r\n",
    "                p1 += 1\r\n",
    "                p2 += 1\r\n",
    "        return diff <= 1\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\"\"\"思路二\"\"\"\r\n",
    "class Solution:\r\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\r\n",
    "        len1, len2 = len(first), len(second)\r\n",
    "        if abs(len1 - len2) > 1:\r\n",
    "            return False\r\n",
    "\r\n",
    "        s1, s2 = 0, 0\r\n",
    "        e1, e2 = len1 - 1, len2 - 1\r\n",
    "        while s1 < len1 and s2 < len2 and first[s1] == second[s2]:\r\n",
    "            s1 += 1\r\n",
    "            s2 += 1\r\n",
    "        prefix_len = s1\r\n",
    "        \r\n",
    "        while s1 <= e1 and s2 <= e2 and first[e1] == second[e2]:\r\n",
    "            e1 -= 1\r\n",
    "            e2 -= 1\r\n",
    "        subfix_len = len2 - e2 - 1\r\n",
    "\r\n",
    "        print(prefix_len, subfix_len)\r\n",
    "\r\n",
    "        if prefix_len + subfix_len < len1 - 1 or prefix_len + subfix_len < len2 - 1:\r\n",
    "            return False\r\n",
    "        return True\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from sortedcontainers import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if len(first) == len(second):\n",
    "            cnt = sum(int(x != y) for x, y in zip(first, second))\n",
    "            return cnt <= 1\n",
    "        if len(first) > len(second):\n",
    "            first, second = second, first\n",
    "        m, n = len(first),len(second)\n",
    "        cnt = 0\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if first[i] != second[j]:\n",
    "                j += 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                i += 1\n",
    "        cnt += max(m-i, n-j)\n",
    "        return cnt <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if len(first)-len(second)>1 or len(first)-len(second)<-1:\n",
    "            return False\n",
    "\n",
    "        p1 = 0\n",
    "        p2 = 0\n",
    "        count = 0\n",
    "        while p1<len(first) and p2<len(second):\n",
    "            if first[p1]==second[p2]:\n",
    "                p1 = p1 + 1\n",
    "                p2 = p2 + 1\n",
    "            else:\n",
    "                print(count, p1, p2)\n",
    "                count = count+1\n",
    "                if count>1:\n",
    "                    return False\n",
    "                if len(first)==len(second):\n",
    "                    p1 = p1 + 1\n",
    "                    p2 = p2 + 1\n",
    "                elif len(first)>len(second):\n",
    "                    p1 = p1+1\n",
    "                else:\n",
    "                    p2 = p2+1\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # if abs(len(first)-len(second))>1:\n",
    "        #     return False\n",
    "\n",
    "        # point1 = 0\n",
    "        # point2 = 0\n",
    "        # count = 0\n",
    "        # while point1<len(first) and point2<len(second):\n",
    "        #     if first[point1]==second[point2]:\n",
    "        #         point1 += 1\n",
    "        #         point2 += 1\n",
    "        #     else:\n",
    "        #         count = count+1\n",
    "        #         if len(first)>len(second):\n",
    "        #             point1 += 1\n",
    "        #         elif len(first)<len(second):\n",
    "        #             point2 += 1\n",
    "        #         else:\n",
    "        #             point1 += 1\n",
    "        #             point2 += 1\n",
    "        #     if count>1:\n",
    "        #         return False\n",
    "        # return True \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first),len(second)\n",
    "        if m<2 and n<2:\n",
    "            return True\n",
    "        a = [[2]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if abs(i-j) <= 1:\n",
    "                    if i==0 and j ==0:\n",
    "                        if first[i] == second[j]:\n",
    "                            a[i][j] = 0\n",
    "                        else:\n",
    "                            a[i][j] = 1\n",
    "                    elif i == 0:\n",
    "                        if first[i] == second[j] or first[i] == second[j-1]:\n",
    "                            a[i][j] = 1\n",
    "                    elif j == 0:\n",
    "                        if first[i] == second[j] or first[i-1] == second[j]:\n",
    "                            a[i][j] = 1\n",
    "                    else:\n",
    "                        if first[i] == second[j]:\n",
    "                            a[i][j] = a[i-1][j-1]\n",
    "                        else:\n",
    "                            a[i][j] = min(a[i-1][j-1],a[i][j-1],a[i-1][j])+1\n",
    "        #print(a)\n",
    "        if a[m-1][n-1]<2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) - len(second)) > 1: return False\n",
    "        if len(first) <= 1 or len(second) <= 1: return True\n",
    "        shorter, longer = [first, second][:] if len(first) < len(second) else [second, first][:]\n",
    "        dp = [[0 for _ in range(len(longer))] for _ in range(len(shorter))]\n",
    "        mark = [False for _ in range(len(longer))]\n",
    "        for i in range(len(shorter)):\n",
    "\n",
    "            for j in range(len(longer)):\n",
    "                # up = dp[i - 1][j] if i - 1 >= 0 else 0\n",
    "                left = dp[i][j - 1] if j - 1 >= 0 else 0\n",
    "                # diag = dp[i-1][j-1] if i - 1 >= 0 and j - 1 >= 0 else 0\n",
    "                pre = dp[i - 1][:j] if i - 1 >= 0 else []\n",
    "                if shorter[i] == longer[j]:\n",
    "                    # dp[i][j:] = [max(up, left) + 1 for _ in range(len(longer) - j)]\n",
    "                    dp[i][j] = max(pre) + 1 if pre else 1\n",
    "                else:\n",
    "                    max_pre = max(pre) if pre else 0\n",
    "                    dp[i][j] = max_pre\n",
    "                    if i > 0 and i == j and len(first) == len(second):\n",
    "                        if dp[i][j] == 0: return False\n",
    "        print(dp)\n",
    "        if len(first) == len(second):\n",
    "            return True if max(dp[-1]) >= len(first) - 1 else False\n",
    "        else:\n",
    "            return True if max(dp[-1]) == len(shorter) else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        # if abs(len(first)-len(second)) >1:\n",
    "        #     return False\n",
    "        # i = 0\n",
    "        # j = 0\n",
    "        # if (len(first)<=2 and len(second)<=1) or (len(first)<=1 and len(second)<=2) or first==second:\n",
    "        #     return True     \n",
    "        # while i<len(first) and j<len(second):\n",
    "        #     if first[i]==second[j]:\n",
    "        #         i+=1\n",
    "        #         j+=1\n",
    "        #     else:\n",
    "\n",
    "        #         if first[i+1:]==second[j:]:\n",
    "        #             return True\n",
    "        #         elif second[j+1:]==first[i:]:\n",
    "        #             return True\n",
    "        #         elif second[j+1:]==first[i+1:]:\n",
    "        #             return True\n",
    "        #         return False\n",
    "        # return True\n",
    "\n",
    "        def dfs( i,  j,  k):\n",
    "            if k < 0:\n",
    "                return False\n",
    "            elif i < 0:\n",
    "                return j < k\n",
    "            elif j < 0:\n",
    "                return i < k\n",
    "            elif first[i] == second[j]:\n",
    "                return dfs(i - 1, j - 1, k)\n",
    "            else:\n",
    "                return dfs(i - 1, j, k - 1) or dfs(i, j - 1, k - 1) or dfs(i - 1, j - 1, k - 1)\n",
    "        return dfs(len(first)-1,len(second)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        '''错误\n",
    "        if abs(len(first)-len(second)) >1:\n",
    "            return False\n",
    "        longstr,shortstr = (first,second) if len(first) >= len(second) else (second,first)\n",
    "        count = 0\n",
    "        if len(shortstr) != len(longstr):\n",
    "            for c in shortstr:\n",
    "                if c not in longstr:\n",
    "                    return False\n",
    "            return True\n",
    "        else:\n",
    "            for i in range(len(longstr)):\n",
    "                if longstr[i] != shortstr[i]:\n",
    "                    count += 1\n",
    "                    if count > 1:\n",
    "                        return False\n",
    "            return True'''\n",
    "        #编辑距离解法   可以通过，但是复杂度太高\n",
    "        '''\n",
    "        first = '#' + first\n",
    "        second = '#' + second\n",
    "        m,n = len(first),len(second)\n",
    "        dp = [[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = i \n",
    "        for i in range(n):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if first[i] == second[j]:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) +1 \n",
    "        if dp[-1][-1] == 1 or dp[-1][-1] == 0:\n",
    "            return True\n",
    "        return False'''\n",
    "        first = '#' + first\n",
    "        second = '#' + second\n",
    "        m,n = len(first),len(second)\n",
    "        if m - n >1:\n",
    "            return False\n",
    "        dp = [[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            dp[i][0] = i \n",
    "        for i in range(n):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if first[i] == second[j]:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) +1 \n",
    "        if dp[-1][-1] == 1 or dp[-1][-1] == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        def dfs( i,  j,  k):\n",
    "            if k < 0:\n",
    "                return False\n",
    "            elif i < 0:\n",
    "                return j < k\n",
    "            elif j < 0:\n",
    "                return i < k\n",
    "            elif first[i] == second[j]:\n",
    "                return dfs(i - 1, j - 1, k)\n",
    "            else:\n",
    "                return dfs(i - 1, j, k - 1) or dfs(i, j - 1, k - 1) or dfs(i - 1, j - 1, k - 1)\n",
    "        return dfs(len(first)-1,len(second)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m = len(first)\n",
    "        n = len(second)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        # dp[0] = [i for i in range(n+1)]\n",
    "        # for i in range(1, m+1):\n",
    "        #     dp[i][0] = i\n",
    "        #     for j in range(1, n+1):\n",
    "        #         if first[i-1] == second[j-1]:\n",
    "        #             dp[i][j] = dp[i-1][j-1]\n",
    "        #         else:\n",
    "        #             dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\n",
    "        # return dp[-1][-1] <= 1\n",
    "\n",
    "        if abs(m - n) > 1:\n",
    "            return False\n",
    "\n",
    "        if m > n:\n",
    "            m, n = n, m\n",
    "            first, second = second, first\n",
    "        for i, (x, y) in enumerate(zip(first, second)):\n",
    "            if x == y:\n",
    "                continue\n",
    "            if m == n:\n",
    "                return first[i+1:] == second[i+1:]\n",
    "            return first[i:] == second[i+1:]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        @cache\n",
    "        def edit(i, j, can_edit):\n",
    "            nonlocal m, n\n",
    "            if i >= m and j >= n:\n",
    "                return True\n",
    "            if i >= m or j >= n:\n",
    "                if can_edit:\n",
    "                    return edit(i+1, j+1, 0)\n",
    "                return False \n",
    "            if first[i] == second[j]:\n",
    "                return edit(i+1, j+1, can_edit)\n",
    "            if can_edit:\n",
    "                return edit(i, j+1, 0) or edit(i+1, j, 0) or edit(i+1, j+1, 0)\n",
    "            return False\n",
    "        \n",
    "        m, n = len(first), len(second)\n",
    "        return edit(0, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        #dp=[[False]*len(second) for i in range(len(first))]\n",
    "        #flag=0\n",
    "        if abs(len(second)-len(first))>1:\n",
    "            return False\n",
    "        dp=[[-1]*len(second) for i in range(len(first))]\n",
    "        self.flag=0\n",
    "        def fun(i,j):\n",
    "            if i<0 and j<0:\n",
    "                return 1       \n",
    "            if i<0 or j<0:\n",
    "                if self.flag==1:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True                \n",
    "            if first[i]==second[j]:\n",
    "                return fun(i-1,j-1)\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            if self.flag==1:\n",
    "                return 0\n",
    "            self.flag=1\n",
    "            if i>j:\n",
    "                dp[i][j]=fun(i-1,j) or fun(i-1,j-1)\n",
    "            elif i<j:\n",
    "                dp[i][j]=fun(i-1,j-1) or fun(i,j-1)\n",
    "            else:\n",
    "                dp[i][j]=fun(i-1,j-1)\n",
    "            return dp[i][j]\n",
    "        return bool(fun(len(first)-1,len(second)-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        @cache\n",
    "        def dfs( i,  j,  k):\n",
    "            if k < 0:\n",
    "                return False\n",
    "            elif i < 0:\n",
    "                return j < k\n",
    "            elif j < 0:\n",
    "                return i < k\n",
    "            elif first[i] == second[j]:\n",
    "                return dfs(i - 1, j - 1, k)\n",
    "            else:\n",
    "                return dfs(i - 1, j, k - 1) or dfs(i, j - 1, k - 1) or dfs(i - 1, j - 1, k - 1)\n",
    "        return dfs(len(first)-1,len(second)-1,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first==second:\n",
    "            return True\n",
    "        m=len(first)\n",
    "        n=len(second)\n",
    "        length=m-n\n",
    "        if abs(m-n)>=2:\n",
    "            return False\n",
    "        dp=[[False for i in range(m)]for j in range(n)]\n",
    "        up=0\n",
    "        down=0\n",
    "        times=1\n",
    "        while up<m and down<n:\n",
    "            if first[up]!=second[down]:\n",
    "                times-=1\n",
    "                if length>0:\n",
    "                    down-=1\n",
    "                elif length<0:\n",
    "                    up-=1\n",
    "            if times<0:\n",
    "                return False\n",
    "            up+=1\n",
    "            down+=1\n",
    "        return True\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        fn = first.__len__()\n",
    "        sn = second.__len__()\n",
    "\n",
    "        dp = [[0] * sn for _ in range(fn)]\n",
    "\n",
    "\n",
    "        for i in range(fn):\n",
    "            for j in range(sn):\n",
    "\n",
    "                if first[i] == second[j]:\n",
    "\n",
    "                    dp[i][j] = 1\n",
    "                    if i - 1 >= 0 and j - 1 >= 0:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)\n",
    "\n",
    "                    if i - 1 >= 0:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "\n",
    "                    if j - 1 >= 0:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i][j - 1])\n",
    "\n",
    "                else:\n",
    "\n",
    "                    if i - 1 >= 0:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i - 1][j])\n",
    "\n",
    "                    if j - 1 >= 0:\n",
    "                        dp[i][j] = max(dp[i][j], dp[i][j - 1])\n",
    "\n",
    "        if fn == 0 or sn == 0:\n",
    "            if abs(fn - sn) <= 1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if fn == sn and max(fn, sn) - dp[fn - 1][sn - 1] <= 1:\n",
    "            if max(fn, sn) - dp[fn - 1][sn - 1] == 0:\n",
    "                return True\n",
    "            else:\n",
    "                d = 0\n",
    "                for i in range(fn):\n",
    "                    if first[i] != second[i]:\n",
    "                        d += 1\n",
    "\n",
    "                if d <= 1:\n",
    "                    return True\n",
    "                return False\n",
    "\n",
    "\n",
    "        if fn != sn and max(fn, sn) - dp[fn - 1][sn - 1] <= 1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    import collections\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        '''a=0\n",
    "        obj1=collections.Counter(first)\n",
    "        obj2=collections.Counter(second)\n",
    "        for key in obj1:\n",
    "            if key not in obj2:\n",
    "                a+=1\n",
    "            if (key not in obj2) & (obj1[key]>1):\n",
    "                a+=1\n",
    "        for key in obj2:\n",
    "            if key not in obj1:\n",
    "                a+=1\n",
    "            if (key not in obj1) & (obj2[key]>1):\n",
    "                a+=1\n",
    "        print(a)\n",
    "        if len(first)==1 & len(second)==1:\n",
    "            return True\n",
    "        if (a==2) & (len(first)==len(second)):\n",
    "            return True\n",
    "        return a<=1'''\n",
    "\n",
    "        # len_1 = len(first)\n",
    "        # len_2 = len(second)\n",
    "        # if abs(len_1-len_2) > 1:\n",
    "        #     return False\n",
    "        # (long_str, short_str) = (first, second) if len_1 > len_2 else (second, first)\n",
    "\n",
    "        # sep = min(len_1, len_2)\n",
    "\n",
    "        # for i in range(sep):\n",
    "        #     if long_str[i] != short_str[i]:\n",
    "        #         sep = i\n",
    "        #         break\n",
    "        \n",
    "        # return long_str[sep+1:] == short_str[sep:] or long_str[sep+1:] == short_str[sep+1:]\n",
    "\n",
    "        lfirst=len(first)\n",
    "        lsecond=len(second)\n",
    "\n",
    "        dp=[[0]*(lsecond+1) for i in range(lfirst+1)]\n",
    "        \n",
    "        for j in range(1,lsecond+1):\n",
    "            dp[0][j]=j\n",
    "        \n",
    "        for i in range(1,lfirst+1):\n",
    "            dp[i][0]=i\n",
    "        \n",
    "        for i in range(1,lfirst+1):\n",
    "            for j in range(1,lsecond+1):\n",
    "                if first[i-1]==second[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])+1\n",
    "        \n",
    "        return True if dp[lfirst][lsecond]<=1 else False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        l1 = len(first)\n",
    "        l2 = len(second)\n",
    "\n",
    "        if abs(l2 - l1) > 1:\n",
    "            return False\n",
    "\n",
    "        dp = [[0] * (l2+1) for _ in range(l1+1)]\n",
    "        for i in range(1, l2+1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1, l1+1):\n",
    "            dp[i][0] = i\n",
    "\n",
    "        for i in range(1, l1+1):\n",
    "            for j in range(1, l2+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "\n",
    "        return dp[-1][-1] < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) - len(second)) > 1:\n",
    "            return False\n",
    "        rec = {} \n",
    "        def do(i, j):\n",
    "            if i < 0:\n",
    "                return j + 1\n",
    "            if j < 0:\n",
    "                return i + 1\n",
    "            \n",
    "            key = f\"{i}_{j}\"\n",
    "            if key in rec:\n",
    "                return rec[key]\n",
    "\n",
    "            if first[i] == second[j]:\n",
    "                return do(i - 1, j - 1)\n",
    "            \n",
    "            res = min(\n",
    "                do(i - 1, j - 1),\n",
    "                do(i - 1, j),\n",
    "                do(i, j - 1)\n",
    "            ) + 1\n",
    "            rec[key] = res\n",
    "            return res\n",
    "        return do(len(first) - 1, len(second) - 1) < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        def minDistance( word1: str, word2: str) -> int:\n",
    "            mem =[[-666 for i in range(len(word2))] for j in range(len(word1))]\n",
    "\n",
    "            def dp(i,j,mem):\n",
    "                if i<0:\n",
    "                    return j+1\n",
    "                if j<0:\n",
    "                    return i+1\n",
    "                if mem[i][j]!= -666 : #说明算过了\n",
    "                    return  mem[i][j]\n",
    "                if word1[i] == word2[j]:\n",
    "                    return dp(i-1,j-1,mem)\n",
    "                else:\n",
    "                    temp = min(  dp(i-1,j-1,mem)+1,\n",
    "                                dp(i,j-1,mem)+1,\n",
    "                                dp(i-1,j, mem)+1  )\n",
    "                    mem[i][j]=temp\n",
    "                    return temp\n",
    "            \n",
    "            return dp(len(word1)-1, len(word2)-1,mem)\n",
    "        return minDistance(first, second) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        # bug!\n",
    "        # count = 0\n",
    "        # i, j = 0, 0\n",
    "        # if abs(len(first) - len(second)) > 2:\n",
    "        #     return False\n",
    "        # while i < len(first) and j < len(second):\n",
    "        #     if first[i] == second[j]:\n",
    "        #         i += 1\n",
    "        #         j += 1\n",
    "        #     elif len(first) == len(second):\n",
    "        #         count += 1\n",
    "        #         i += 1\n",
    "        #         j += 1\n",
    "        #     elif len(first) != len(second):\n",
    "        #         if len(first)>len(second):\n",
    "        #             i += 1\n",
    "        #         else:\n",
    "        #             j += 1\n",
    "        #         count += 1\n",
    "        #     if count > 1:\n",
    "        #         return False\n",
    "        # if count > 1:\n",
    "        #         return False\n",
    "        # return i==len(first) and j ==len(second)\n",
    "\n",
    "\n",
    "        # 编辑距离 备忘录递归\n",
    "        m, n = len(first), len(second)\n",
    "        memo = [[float('inf')] * n for _ in range(m)]\n",
    "        def dp(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return i + 1 if i >= 0 else j + 1\n",
    "            if memo[i][j] != float('inf'):return memo[i][j]\n",
    "            if first[i] == second[j]:\n",
    "                memo[i][j] = dp(i-1, j-1)\n",
    "            else:\n",
    "                memo[i][j] = min(dp(i-1, j-1), dp(i-1, j), dp(i, j-1)) + 1\n",
    "            return memo[i][j]\n",
    "        \n",
    "        return dp(m-1, n-1) < 2\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) -len(second)) >=2:\n",
    "            return False \n",
    "\n",
    "        def minDistance( word1: str, word2: str) -> int:\n",
    "            mem =[[-666 for i in range(len(word2))] for j in range(len(word1))]\n",
    "\n",
    "            def dp(i,j,mem):\n",
    "                if i<0:\n",
    "                    return j+1\n",
    "                if j<0:\n",
    "                    return i+1\n",
    "                if mem[i][j]!= -666 : #说明算过了\n",
    "                    return  mem[i][j]\n",
    "                if word1[i] == word2[j]:\n",
    "                    return dp(i-1,j-1,mem)\n",
    "                else:\n",
    "                    temp = min(  dp(i-1,j-1,mem)+1,\n",
    "                                dp(i,j-1,mem)+1,\n",
    "                                dp(i-1,j, mem)+1  )\n",
    "                    mem[i][j]=temp\n",
    "                    return temp\n",
    "            \n",
    "            return dp(len(word1)-1, len(word2)-1,mem)\n",
    "        return minDistance(first, second) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) -len(second)) >=2:\n",
    "            return False \n",
    "\n",
    "        def minDistance( word1: str, word2: str) -> int:\n",
    "            mem =[[-666 for i in range(len(word2))] for j in range(len(word1))]\n",
    "\n",
    "            def dp(i,j,mem):\n",
    "                if i<0:\n",
    "                    return j+1\n",
    "                if j<0:\n",
    "                    return i+1\n",
    "                if mem[i][j]!= -666 : #说明算过了\n",
    "                    return  mem[i][j]\n",
    "                if word1[i] == word2[j]:\n",
    "                    return dp(i-1,j-1,mem)\n",
    "                else:\n",
    "                    temp = min(  dp(i-1,j-1,mem)+1,\n",
    "                                dp(i,j-1,mem)+1,\n",
    "                                dp(i-1,j, mem)+1  )\n",
    "                    mem[i][j]=temp\n",
    "                    return temp\n",
    "            \n",
    "            return dp(len(word1)-1, len(word2)-1,mem)\n",
    "        return minDistance(first, second) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) -len(second)) >=2:\n",
    "            return False \n",
    "\n",
    "        def minDistance( word1: str, word2: str) -> int:\n",
    "            mem =[[-666 for i in range(len(word2))] for j in range(len(word1))]\n",
    "\n",
    "            def dp(i,j,mem):\n",
    "                if i<0:\n",
    "                    return j+1\n",
    "                if j<0:\n",
    "                    return i+1\n",
    "                if mem[i][j]!= -666 : #说明算过了\n",
    "                    return  mem[i][j]\n",
    "                if word1[i] == word2[j]:\n",
    "                    return dp(i-1,j-1,mem)\n",
    "                else:\n",
    "                    temp = min(  dp(i-1,j-1,mem)+1,\n",
    "                                dp(i,j-1,mem)+1,\n",
    "                                dp(i-1,j, mem)+1  )\n",
    "                    mem[i][j]=temp\n",
    "                    return temp\n",
    "            \n",
    "            return dp(len(word1)-1, len(word2)-1,mem)\n",
    "        return minDistance(first, second) <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        memo = {}\n",
    "  \n",
    "        def lwstBT(i , j):\n",
    "\n",
    "            if (i,j) in self.memo:\n",
    "                return self.memo[(i,j)]\n",
    "            \n",
    "            if i == -1:\n",
    "                return j +1\n",
    "            if j == -1:\n",
    "                return i+1\n",
    "\n",
    "            if first[i] == second[j]:\n",
    "                x = lwstBT(i-1, j-1)\n",
    "            else:\n",
    "                x =  min(lwstBT(i,j-1) + 1, lwstBT(i-1,j) + 1, lwstBT(i-1,j-1)+1)\n",
    "            self.memo[(i,j)] = x\n",
    "            return self.memo[(i,j)]\n",
    "\n",
    "        self.memo = {}\n",
    "        \n",
    "        return lwstBT(len(first)-1,len(second)-1)<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        memo = {}\n",
    "  \n",
    "        def lwstBT(i , j):\n",
    "\n",
    "            if (i,j) in self.memo:\n",
    "                return self.memo[(i,j)]\n",
    "            \n",
    "            if i == -1:\n",
    "                return j +1\n",
    "            if j == -1:\n",
    "                return i+1\n",
    "\n",
    "            if first[i] == second[j]:\n",
    "                x = lwstBT(i-1, j-1)\n",
    "            else:\n",
    "                x =  min(lwstBT(i,j-1) + 1, lwstBT(i-1,j) + 1, lwstBT(i-1,j-1)+1)\n",
    "            self.memo[(i,j)] = x\n",
    "            return self.memo[(i,j)]\n",
    "\n",
    "        self.memo = {}\n",
    "        \n",
    "        return lwstBT(len(first)-1,len(second)-1)<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        lens1 = len(first)\n",
    "        lens2 = len(second)\n",
    "        memo = [[0 for _ in range(lens2)]for _ in range(lens1)]\n",
    "        def compute(i,j):\n",
    "            if i<0:\n",
    "                return j+1\n",
    "            elif j<0:\n",
    "                return i+1\n",
    "            elif memo[i][j]!=0:\n",
    "                return memo[i][j]\n",
    "            elif memo[i][j]>1:\n",
    "                return False\n",
    "            if first[i]==second[j]:\n",
    "                memo[i][j] = compute(i-1,j-1)\n",
    "            else:\n",
    "                memo[i][j] = min(\n",
    "                    compute(i-1,j)+1,compute(i,j-1)+1,compute(i-1,j-1)+1\n",
    "                )\n",
    "            return memo[i][j]\n",
    "        return compute(lens1-1,lens2-1)<=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n = len(first)\n",
    "        m = len(second)\n",
    "        mem = {}\n",
    "        def dp(i, j):\n",
    "            if i == -1:\n",
    "                return j + 1\n",
    "            if j == -1:\n",
    "                return i + 1\n",
    "\n",
    "            if (i, j) in mem:\n",
    "                return mem[i, j]\n",
    "            if first[i] == second[j]:\n",
    "                mem[i, j] = dp(i - 1, j - 1)\n",
    "                return mem[i, j]\n",
    "            mem[i, j] = min(dp(i - 1, j) + 1, dp(i, j - 1) + 1, dp(i - 1, j - 1) + 1)\n",
    "            return mem[i, j]\n",
    "        return dp(n - 1, m - 1) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        \n",
    "        N,M = len(first),len(second)\n",
    "        dp = [[-1]*M for _ in range(N)]\n",
    "        def dfs(i,j):\n",
    "            nonlocal first\n",
    "            nonlocal second\n",
    "            if i<0 or j<0:\n",
    "                return max(i+1,j+1)\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j] \n",
    "            if first[i] == second[j]:\n",
    "                dp[i][j] = dfs(i-1,j-1)\n",
    "                return dp[i][j]\n",
    "            else:\n",
    "                dp[i][j] = min(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1))+1\n",
    "                return dp[i][j] \n",
    "        # dfs(N-1,M-1)\n",
    "        # print(dp)\n",
    "        return False if dfs(N-1,M-1)>1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m,n = len(first), len(second)\n",
    "        if first==second or m==n==1:return True\n",
    "        if m*n==0: return m+n==1\n",
    "        if m*n==2: return first[0]==second[-1] or first[0]==second[0] or first[-1]==second[0] or first[-1]==second[-1]\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        dp[0][1] = True if first[0]==second[1] else first[0]==second[0]\n",
    "        dp[1][0] = True if first[1]==second[0] else first[0]==second[0]\n",
    "        flag = False if first[0]==second[0] else True\n",
    "        for i in range(1,m):\n",
    "            for j in range(max(i-1,1),n):\n",
    "                if j-i>1:break\n",
    "                if first[i]==second[j]:\n",
    "                    # print(i,j)\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    # if flag:return False\n",
    "                    if i==j:\n",
    "                        dp[i][j] = dp[i-1][j-1] if not flag else False\n",
    "                        flag=True\n",
    "                    else:\n",
    "                        # print(i,j)\n",
    "                        tmp = min(i,j)\n",
    "                        dp[i][j] = first[:tmp+1]==second[:tmp+1]\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n,m=len(first),len(second)\n",
    "        self.s1,self.s2=first,second\n",
    "        self.dp=[[-1]*(m+1) for _ in range(n+1)]\n",
    "        if self.solve(n,m)<=1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def solve(self,n,m):\n",
    "        if n==0 or m==0:\n",
    "            return n+m\n",
    "        if self.dp[n][m]!=-1:\n",
    "            return self.dp[n][m]\n",
    "        if self.s1[n-1]==self.s2[m-1]:\n",
    "            self.dp[n][m]=self.solve(n-1,m-1)\n",
    "        else:\n",
    "            self.dp[n][m]=min(self.solve(n-1,m)+1,self.solve(n,m-1)+1,self.solve(n-1,m-1)+1)\n",
    "        return self.dp[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m,n = len(first), len(second)\n",
    "        if first==second or m==n==1:return True\n",
    "        if m*n==0: return m+n==1\n",
    "        if m*n==2: return first[0]==second[-1] or first[0]==second[0] or first[-1]==second[0] or first[-1]==second[-1]\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "        dp[0][0] = True\n",
    "        dp[0][1] = True if first[0]==second[1] else first[0]==second[0]\n",
    "        dp[1][0] = True if first[1]==second[0] else first[0]==second[0]\n",
    "        flag = False if first[0]==second[0] else True\n",
    "        for i in range(1,m):\n",
    "            # if i>=n:break\n",
    "            for j in range(max(i-1,1),n):\n",
    "                if j-i>1:break\n",
    "                if first[i]==second[j]:\n",
    "                    # print(i,j)\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    # if flag:return False\n",
    "                    if i==j:\n",
    "                        dp[i][j] = dp[i-1][j-1] if not flag else False\n",
    "                        flag=True\n",
    "                    else:\n",
    "                        # print(i,j)\n",
    "                        tmp = min(i,j)\n",
    "                        dp[i][j] = first[:tmp+1]==second[:tmp+1]\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1][-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if not first or not second:\n",
    "            return len(first) + len(second) <= 1\n",
    "\n",
    "        m , n = len(first), len(second)\n",
    "        res = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            res[i][0] = i\n",
    "\n",
    "        for i in range(n):\n",
    "            res[0][i] = i\n",
    "            \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if first[i - 1] == second[j - 1]:\n",
    "                    res[i][j] = res[i - 1][j - 1]\n",
    "                else:\n",
    "                    res[i][j] = min([res[i - 1][j], res[i - 1][j - 1], res[i][j - 1]]) + 1\n",
    "\n",
    "        # for line in res:\n",
    "        #     print(line)\n",
    "            \n",
    "        return res[-1][-1] <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first) + 1, len(second) + 1\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i - 1][0] + 1\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j - 1] + 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "        return dp[-1][-1] <=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n1,n2 = len(first),len(second)\n",
    "        dp = [[0]*(n2+1) for i in range(1+n1)]\n",
    "\n",
    "        for i in range(1,n1+1):\n",
    "            dp[i][0]=i\n",
    "        for j in range(1,n2+1):\n",
    "            dp[0][j]=j\n",
    "        \n",
    "        for i in range(1,n1+1):\n",
    "            for j in range(1,n2+1):\n",
    "                if first[i-1]==second[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1\n",
    "        return dp[-1][-1]<=1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        def dp(i, j):\n",
    "            nonlocal memo\n",
    "            if (i, j) in memo: return memo[(i,j)]\n",
    "            if i < 0: return j + 1\n",
    "            if j < 0: return i + 1\n",
    "            if first[i] == second[j]:\n",
    "                memo[(i, j)] = dp(i-1, j-1)\n",
    "            else:\n",
    "                memo[(i, j)] = min(dp(i, j-1), dp(i-1, j-1), dp(i-1, j))+1\n",
    "            return memo[(i, j)]\n",
    "        memo = dict()\n",
    "        return dp(len(first)-1, len(second)-1) <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n1 = len(first)\n",
    "        n2 = len(second)\n",
    "        if (n1 - n2) > 1 or (n2 - n1) > 1:\n",
    "            return False\n",
    "        dp = [[0] * (n2+1) for _ in range(n1+1)]\n",
    "        for i in range(n1+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n2+1):\n",
    "            dp[0][j] = j\n",
    "        \n",
    "        for i in range(1, n1+1):\n",
    "            for j in range(1, n2+1):\n",
    "                left = dp[i-1][j] + 1\n",
    "                down = dp[i][j-1] + 1\n",
    "                left_down = dp[i-1][j-1]\n",
    "                if first[i-1] != second[j-1]:\n",
    "                    left_down += 1\n",
    "                dp[i][j] = min(left_down, left, down)\n",
    "        \n",
    "        return True if dp[-1][-1] <= 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m,n = len(first),len(second)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j] = 0\n",
    "                elif i==0:\n",
    "                    dp[i][j] = dp[i][j-1]+1\n",
    "                elif j==0:\n",
    "                    dp[i][j] = dp[i-1][j]+1\n",
    "                else:\n",
    "                    if first[i-1]==second[j-1]:\n",
    "                        dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1\n",
    "        return dp[-1][-1]<2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if first==\"\":\n",
    "            return True if len(second)<=1 else False\n",
    "        if second==\"\":\n",
    "            return True if len(first)<=1 else False\n",
    "        if first==\"\" and second == \"\":\n",
    "            return True\n",
    "        if self.minEdit(first, second) <= 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def minEdit(self, first, second):\n",
    "        m = len(first)\n",
    "        n = len(second)  \n",
    "\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        dp[0][0] = 0 if (first[0]==second[0]) else 1\n",
    "        for i in range(1, m):\n",
    "            if first[i] == second[0]:\n",
    "                dp[i][0] = dp[i-1][0]\n",
    "            else:\n",
    "                dp[i][0] = dp[i-1][0] + 1\n",
    "        for j in range(1, n):\n",
    "            if first[0] == second[j]:\n",
    "                dp[0][j] = dp[0][j-1]\n",
    "            else:\n",
    "                dp[0][j] = dp[0][j-1] + 1\n",
    "        #dp[i][j]=min(dp[i][j-1],dp[i-1],dp[i-1][j-1])+1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if first[i] == second[j]:\n",
    "                    dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1,dp[i-1][j-1])\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1\n",
    "        return dp[m-1][n-1]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        # minimum edit distance\n",
    "\n",
    "        '''\n",
    "        dp[i][j] represents for the MED for the first i chars and Second j chars\n",
    "        dp[0][0] = 0 \n",
    "        0 <= i < n, 1 <= j < m\n",
    "\n",
    "\n",
    "        '''\n",
    "        \n",
    "        n, m= len(first), len(second)\n",
    "\n",
    "        if n==0:\n",
    "            return m <= 1\n",
    "        if m ==0:\n",
    "            return n <= 1\n",
    "        dp = [[0] * m for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == 0 and j == 0:\n",
    "                    if first[i] == second[j]:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = 1\n",
    "\n",
    "                elif i == 0:\n",
    "\n",
    "                    if first[i] == second[j]:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1] + 1\n",
    "                \n",
    "                elif j == 0:\n",
    "\n",
    "                    if first[i] == second[j]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j] + 1\n",
    "\n",
    "                else:\n",
    "                    if first[i] == second[j]:\n",
    "                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n",
    "        # print(dp)\n",
    "        return dp[n-1][m-1] <= 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n1 = len(first)\n",
    "        n2 = len(second)\n",
    "        if abs(n1-n2)>=2:\n",
    "            return False\n",
    "        # 动态规划 编辑距离\n",
    "        dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]\n",
    "        for i in range(n1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n2):\n",
    "            dp[0][j] = j\n",
    "        for i in range(n1):\n",
    "            for j in range(n2):\n",
    "                if first[i]==second[j]:\n",
    "                    dp[i+1][j+1] = dp[i][j]\n",
    "                else:\n",
    "                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j])+1\n",
    "        if dp[-1][-1]<=1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        info_dict=dict()\n",
    "        info_dict[\"0_0\"]=0\n",
    "        info_dict[\"0_1\"]=1\n",
    "        info_dict[\"1_0\"]=1\n",
    "        def recur(i, j):\n",
    "            if i==0 or j==0:\n",
    "                if i+j!=0:\n",
    "                    return i+j\n",
    "            if \"{}_{}\".format(i, j) not in info_dict:\n",
    "                if first[i-1]==second[j-1]:\n",
    "                    info_dict[\"{}_{}\".format(i, j)]=recur(i-1, j-1)\n",
    "                else:\n",
    "                    info_dict[\"{}_{}\".format(i, j)]=1+min(\n",
    "                        recur(i-1, j), #删除一个\n",
    "                        recur(i, j-1), #插入一个\n",
    "                        recur(i-1, j-1) #替换一个\n",
    "                    )\n",
    "            # print(info_dict)\n",
    "            return info_dict[\"{}_{}\".format(i, j)]\n",
    "        return recur(len(first), len(second))<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        dp = [[0]*(len(second)+1) for i in range(len(first)+1)]\n",
    "        for i in range(len(first)+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(len(second)+1):\n",
    "            dp[0][i] = i\n",
    "        for x in range(1, len(first)+1):\n",
    "            for y in range(1, len(second)+1):\n",
    "                if first[x-1]==second[y-1]:\n",
    "                    dp[x][y] = dp[x-1][y-1]\n",
    "                else:\n",
    "                    dp[x][y] = min(dp[x-1][y], dp[x][y-1], dp[x-1][y-1])+1\n",
    "        if dp[len(first)][len(second)]<=1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        F = [[0]*(len(first)+1) for i in range(len(second)+1)]\n",
    "        for i in range(1,len(first)+1):\n",
    "            F[0][i] = F[0][i-1]+1\n",
    "        for i in range(1,len(second)+1):\n",
    "            F[i][0] = F[i-1][0]+1\n",
    "        for i in range(1,len(second)+1):\n",
    "            for j in range(1,len(first)+1):\n",
    "                if first[j-1] == second[i-1]:\n",
    "                    F[i][j] = F[i-1][j-1]\n",
    "                else:\n",
    "                    F[i][j] = min(F[i-1][j-1],F[i-1][j],F[i][j-1]) + 1\n",
    "        # for i in F:\n",
    "        #     print(i)\n",
    "        return False if F[-1][-1] > 1 else True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        # dp[i][j]: first[:i-1]与second[:j-1]的最小编辑距离\n",
    "        dp = [[0]*(len(second)+1) for _ in range(len(first)+1)]\n",
    "\n",
    "        for i in range(len(first)+1):\n",
    "            dp[i][0] = i\n",
    "        \n",
    "        for j in range(len(second)+1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "\n",
    "        for i in range(1, len(first)+1):\n",
    "            for j in range(1, len(second)+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n",
    "                \n",
    "                # if dp[i][j] > 1:\n",
    "                #     return False\n",
    "        \n",
    "\n",
    "        return False if dp[-1][-1]>1 else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        # 等长，只差一个字符\n",
    "        # 不等长，全匹配，多一个字符\n",
    "        \n",
    "        n = len(first)\n",
    "        m = len(second)\n",
    "        if abs(n-m) >= 2:\n",
    "            return False\n",
    "\n",
    "        dp = [[None] * (m+1) for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(m+1):\n",
    "            dp[0][j] = j\n",
    "        # print(dp)\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if first[i-1] == second[j-1]:        \n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]+1, dp[i][j-1]+1)\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1\n",
    "\n",
    "        return True if dp[n][m] <= 1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        # 求编辑距离\n",
    "        if first == second:\n",
    "            return True\n",
    "        m = len(first)\n",
    "        n = len(second)\n",
    "\n",
    "        dp = [[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(m+1):\n",
    "            for j in range(n+1):\n",
    "                if i == 0 and j==0:\n",
    "                    continue\n",
    "                elif i == 0:\n",
    "                    dp[i][j] = dp[i][j-1] + 1\n",
    "                elif j == 0:\n",
    "                    dp[i][j] = dp[i-1][j] + 1\n",
    "                elif first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1\n",
    "        # print(dp[m])\n",
    "        # print(dp)\n",
    "        return dp[m][n] <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,n+1):\n",
    "            dp[0][i] = i\n",
    "        for i in range(1,m+1):\n",
    "            dp[i][0] = i\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1\n",
    "        return dp[m][n] <= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        if m * n == 0:\n",
    "            return (m + n) <= 1\n",
    "\n",
    "        for i in range(m + 1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(n + 1):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if first[i-1] != second[j-1]:\n",
    "                    move = 1\n",
    "                else:\n",
    "                    move = 0\n",
    "                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + move)\n",
    "\n",
    "        return dp[-1][-1] == 1 or dp[-1][-1] == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        if abs(m-n) > 1:\n",
    "            return False\n",
    "        if m == 0 or n == 0:\n",
    "            return True\n",
    "        memo = [[-1]*n for _ in range(m)]\n",
    "        \n",
    "        def dp(i, j):\n",
    "            if i == m:\n",
    "                return n-j\n",
    "            if j == n:\n",
    "                return m-i\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "            \n",
    "            if first[i] == second[j]:\n",
    "                memo[i][j] = dp(i+1, j+1)\n",
    "            else:\n",
    "                memo[i][j] = min(dp(i+1, j), dp(i, j+1), dp(i+1, j+1)) + 1\n",
    "            \n",
    "            return memo[i][j]\n",
    "        \n",
    "        dp(0,0)\n",
    "        return memo[0][0] <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class EditDist:\n",
    "    def __init__(self, word1, word2):\n",
    "        m, n = len(word1), len(word2)\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == m: return n-j\n",
    "            if j == n: return m-i\n",
    "            if word1[i] == word2[j]: return f(i+1, j+1)\n",
    "            return min(f(i+1, j), f(i, j+1), f(i+1, j+1)) + 1\n",
    "        self.dist = f(0, 0)\n",
    "\n",
    "    def get_edit_dist(self):\n",
    "        return self.dist\n",
    "\n",
    "# if __name__==\"__main__\":\n",
    "#     ed = EditDist(word1, word2)\n",
    "#     ed.get_edit_dist()\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        ed = EditDist(first, second)\n",
    "        return ed.get_edit_dist() <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        len1 = len(first)+1\n",
    "        len2 = len(second)+1\n",
    "\n",
    "        dp = []\n",
    "        for i in range(len1):\n",
    "            dp.append([])\n",
    "            for j in range(len2):\n",
    "                dp[i].append(0)\n",
    "        \n",
    "        for i in range(len1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(len2):\n",
    "            dp[0][j] = j\n",
    "\n",
    "        print (dp)\n",
    "        for i in range(1, len1):\n",
    "            for j in range(1, len2):\n",
    "                dp[i][j] = dp[i-1][j-1]+(first[i-1]!=second[j-1])\n",
    "                \n",
    "                tmp = min(dp[i-1][j], dp[i][j-1])+1\n",
    "                dp[i][j] = min(dp[i][j], tmp)\n",
    "                # print (i, j, dp[i][j])\n",
    "        \n",
    "        return dp[len1-1][len2-1]<=1\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "\n",
    "        m, n = len(first), len(second)\n",
    "\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = dp[i-1][0] + 1\n",
    "        for j in range(1, n+1):\n",
    "            dp[0][j] = dp[0][j-1] + 1\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)\n",
    "\n",
    "        print(dp)\n",
    "        return dp[-1][-1] < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(maxsize=None)\n",
    "        def edit(a, b):\n",
    "            if not a: \n",
    "                return len(b)\n",
    "            if not b: \n",
    "                return len(a)\n",
    "            if a[0] == b[0]: \n",
    "                return edit(a[1:], b[1:])\n",
    "            return 1 + min(edit(a[1:], b), edit(a, b[1:]), edit(a[1:], b[1:]))\n",
    "        return edit(first, second) < 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n = len(first)\n",
    "        m = len(second)\n",
    "        dp = [[0 for i in range(m+1)] for j in range(n+1)]\n",
    "       \n",
    "        for i in range(n+1):\n",
    "            dp[i][0] = i \n",
    "        for i in range(m+1):\n",
    "            dp[0][i] = i \n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1\n",
    "        print(dp)\n",
    "        return dp[-1][-1] < 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        def EditDistance(s1, s2):\n",
    "            dp = [[0 for _ in range(len(s2)+1)] for _ in range(len(s1)+1)]\n",
    "            for i in range(len(s1)):\n",
    "                dp[i+1][0] = i+1\n",
    "            for j in range(len(s2)):\n",
    "                dp[0][j+1] = j+1\n",
    "            for i in range(len(s1)):\n",
    "                for j in range(len(s2)):\n",
    "                    dp[i+1][j+1] = min(\n",
    "                        dp[i][j] + 1 if s1[i] != s2[j] else dp[i][j],\n",
    "                        dp[i+1][j] + 1,\n",
    "                        dp[i][j+1] + 1\n",
    "                    )\n",
    "            return dp\n",
    "        ed = EditDistance(first, second)\n",
    "        print(ed)\n",
    "        return  ed[-1][-1]<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        if abs(len(first) - len(second)) >= 2:\n",
    "            return False\n",
    "        if max(len(first), len(second)) == 1 or first == second:\n",
    "            return True\n",
    "        dp = [[i for i in range(len(second) + 1)] if j == 0 else [0] * (len(second) + 1) for j in range(len(first) + 1)]\n",
    "        for j in range(len(first) + 1):\n",
    "            dp[j][0] = j\n",
    "        for i in range(1, len(first) + 1):\n",
    "            for j in range(1, len(second) + 1):\n",
    "                flag = 0 if first[i - 1] == second[j - 1] else 1\n",
    "                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + flag)\n",
    "                # print(dp)\n",
    "                # if dp[i][j] > 1:\n",
    "                #     return False\n",
    "        print(dp)\n",
    "        return dp[len(first)][len(second)] <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        if m == 0 or n == 0:\n",
    "            if abs(m-n)<=1:\n",
    "                return True\n",
    "            return False\n",
    "        # m:first\n",
    "        # n:second\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        tmp = 0\n",
    "        for i in range(m):\n",
    "            if first[i] == second[0]:\n",
    "                tmp = 1\n",
    "            dp[i][0] = i+1-tmp\n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            if second[i] == first[0]:\n",
    "                tmp = 1\n",
    "            dp[0][i] = i+1-tmp\n",
    "        print(dp)\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if first[i] == second[j]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\n",
    "        print(dp)\n",
    "        if dp[-1][-1] <= 1:\n",
    "            return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n,m=len(first),len(second)\n",
    "        dp=[[0 for j in range(m+1)]for i in range(n+1)]\n",
    "        for j in range(m+1):\n",
    "            dp[0][j]=j\n",
    "        for i in range(n+1):\n",
    "            dp[i][0]=i\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if first[i]==second[j]:\n",
    "                    dp[i+1][j+1]=min(dp[i][j],dp[i+1][j]+1, dp[i][j+1]+1)\n",
    "                else:\n",
    "                    dp[i+1][j+1]=min(dp[i][j]+1,dp[i+1][j]+1, dp[i][j+1]+1)\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]<=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        for i in range(n + 1):\n",
    "            dp[0][i] = i\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            dp[i][0] = i\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i - 1][j - 1] if first[i - 1] == second[j - 1] else \\\n",
    "                    min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1\n",
    "        \n",
    "        return dp[m][n] <= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        n = len(first)\n",
    "        m = len(second)\n",
    "        if n * m ==0:\n",
    "            return abs(n-m)<2\n",
    "        dp = [[0 for _ in range(m+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            dp[i][0] = i\n",
    "        for j in range(1, m+1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1])\n",
    "                else: \n",
    "                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)\n",
    "        return dp[n][m]<2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, word1: str, word2: str) -> bool:\n",
    "        n = len(word1)\n",
    "        m = len(word2)\n",
    "        \n",
    "        # 有一个字符串为空串\n",
    "        if n * m == 0:\n",
    "            return n + m <= 1\n",
    "        \n",
    "        # DP 数组\n",
    "        D = [ [0] * (m + 1) for _ in range(n + 1)]\n",
    "        \n",
    "        # 边界状态初始化\n",
    "        for i in range(n + 1):\n",
    "            D[i][0] = i\n",
    "        for j in range(m + 1):\n",
    "            D[0][j] = j\n",
    "        \n",
    "        # 计算所有 DP 值\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                left = D[i - 1][j] + 1\n",
    "                down = D[i][j - 1] + 1\n",
    "                left_down = D[i - 1][j - 1] \n",
    "                if word1[i - 1] != word2[j - 1]:\n",
    "                    left_down += 1\n",
    "                D[i][j] = min(left, down, left_down)\n",
    "        \n",
    "        return D[n][m] <= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def oneEditAway(self, first: str, second: str) -> bool:\n",
    "        m, n = len(first), len(second)\n",
    "        dp = [[1]*(n+1) for _ in range(m+1)]\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = j\n",
    "        for i in range(1, m+1):\n",
    "            dp[i][0] = i\n",
    "            for j in range(1, n+1):\n",
    "                if first[i-1] == second[j-1]:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + 1, dp[i][j-1] + 1)\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1)\n",
    "        return dp[-1][-1] <= 1\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
